package simple;

import java.util.ArrayList;
import java.util.Map;

/**
 * @author 杜伟毅
 * @version 1.0
 * @since 2025/10/07
 * <p>
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "()"
 * <p>
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "()[]{}"
 * <p>
 * 输出：true
 * <p>
 * 示例 3：
 * <p>
 * 输入：s = "(]"
 * <p>
 * 输出：false
 * <p>
 * 示例 4：
 * <p>
 * 输入：s = "([])"
 * <p>
 * 输出：true
 * <p>
 * 示例 5：
 * <p>
 * 输入：s = "([)]"
 * <p>
 * 输出：false
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 * <p>
 * 思路：
 * 1.如果字符串长度为单数，直接返回false
 * 2.遍历整个字符串，
 * 左括号处理：遇到左边的符号，就放进数组中，
 * 右括号处理：遇到右括号时，如果数组为空->无效，
 * 如果当前右括号与数组最左值不匹配->无效
 * 如果当前右括号与数组最左值匹配，则删除该值，继续对比其他的左括号
 * <p>
 * 如果数组为空 → 所有括号都匹配成功（有效）
 * 如果数组非空 → 有未匹配的左括号（无效）
 * <p>
 * 注意：在删除数组内元素时应该用strs.remove(strs.size()-1);
 * 而不是strs.remove(strs.getLast());
 * 因为strs.getLast()是Character last = strs.getLast(); 确实是能够取到最后一个值，但由于返回的是取到的是Character类型，如 '['
 * 当数组里有[ '[' '(' '[' ],
 * 当使用remove方法删除时，正常来讲时删除最后一个'['，但实际时删除最早匹配的那个，既第一个'['，所以只能使用strs.size()-1 来定位数组，而不是用strs.getLast()
 * <p>
 * 不要瞎鸡儿信IDEA给的优化方法
 */
public class BracketValidator {

//    public boolean isValid(String s) {
//        //如果长度不是双数就是不匹配，直接返回
//        if (s.length() % 2 != 0) {
//            return false;
//        }
//        ArrayList<Character> strs = new ArrayList<>(s.length());
//
//        for (int i = 0; i < s.length(); i++) {
//            //遇到左边的符号，就放进数组中，
//            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
//                strs.add(s.charAt(i));
//                continue;
//            }
//
//            //遇到右括号时，如果数组为空->无效
//            if (strs.isEmpty()) {
//                return false;
//            }
//
//            if (s.charAt(i) == ')') {
//                if (strs.getLast() != '(') {
//                    //如果当前右括号与数组最左值不匹配->无效
//                    return false;
//                }
//                //如果当前右括号与数组最左值匹配，则删除该值，继续对比其他的左括号
//                strs.remove(strs.size()-1);
//            } else if (s.charAt(i) == ']') {
//                if (strs.getLast() != '[') {
//                    //如果当前右括号与数组最左值不匹配->无效
//                    return false;
//                }
//                //如果当前右括号与数组最左值匹配，则删除该值，继续对比其他的左括号
//                strs.remove(strs.size()-1);
//            } else if (s.charAt(i) == '}') {
//                if (strs.getLast() != '{') {
//                    //如果当前右括号与数组最左值不匹配->无效
//                    return false;
//                }
//                //如果当前右括号与数组最左值匹配，则删除该值，继续对比其他的左括号
//                strs.remove(strs.size()-1);
//            }
//        }
//
//        return strs.isEmpty();
//    }


    public boolean isValid(String s) {
        //如果长度不是双数就是不匹配，直接返回
        if (s.length() % 2 != 0) {
            return false;
        }

        // 括号映射表
        Map<Character, Character> map = Map.of(
                ')', '(',
                ']', '[',
                '}', '{'
        );

        ArrayList<Character> strs = new ArrayList<>(s.length());

        for (char c : s.toCharArray()) {
            //遇到左边的符号，就放进数组中，
            if (c == '(' || c == '[' || c == '{') {
                strs.add(c);
            } else {
                //遇到右括号时，如果数组为空->无效
                if (strs.isEmpty()) return false;
                if (strs.getLast() != map.get(c)) return false;
                strs.remove(strs.size() - 1);
            }
        }

        return strs.isEmpty();
    }

    public static void main(String[] args) {
        String str = "()";
//        String str = "()[]{}";
//        String str="(]";
//        String str="([])";
//        String str="([)]";

//        String str = "[([]])";

        BracketValidator bracketValidator = new BracketValidator();
        System.out.println(bracketValidator.isValid(str));
    }
}
